package com.zbxx.leetcode.tree;

import com.zbxx.leetcode.struct.TreeNode;

import java.util.*;

/**
 * 865具有所有最深节点的子树
 *
 * @author wanrj
 * @date 2023/6/12
 */
public class subtreeWithAllDeepest {


    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        //先bfs 看看最深层数和最深层节点个数 如果最深一个 直接返回
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode last = null;
        deque.offer(root);
        deque.offer(null);
        int depth = 0;
        int lastNum = 0;
        while (!deque.isEmpty()) {
            TreeNode n = deque.poll();
            if (n == null) {
                depth++;
                if (!deque.isEmpty()) {
                    lastNum = 0;
                    deque.offer(null);
                }
                continue;
            }
            last = n;
            lastNum++;
            if (n.left != null) {
                deque.offer(n.left);
            }
            if (n.right != null) {
                deque.offer(n.right);
            }
        }
        if (lastNum == 1) {
            return last;
        }
        //不为空 dfs
        List<TreeNode> nodes = new ArrayList<>(depth);
        dfs(root, nodes, new ArrayList<>(depth), --depth, 0);
        for (TreeNode node : nodes) {
            if (node.val == -1) {
                return root;
            }
            root = node;
        }
        return root;
    }

    public void dfs(TreeNode node, List<TreeNode> nodes, List<TreeNode> current, int depth, int currentDepth) {
        current.add(node);
        if (depth == currentDepth) {
            if (nodes.isEmpty()) {
                nodes.addAll(current);
                return;
            }
            for (int i = 0; i < current.size(); i++) {
                if (!Objects.equals(nodes.get(i), current.get(i))) {
                    nodes.set(i, new TreeNode(-1));
                    return;
                }
            }
            return;
        }
        if (node.left != null) {
            dfs(node.left, nodes, current, depth, currentDepth + 1);
            current.remove(currentDepth + 1);
        }
        if (node.right != null) {
            dfs(node.right, nodes, current, depth, currentDepth + 1);
            current.remove(currentDepth + 1);
        }
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        subtreeWithAllDeepest s = new subtreeWithAllDeepest();
        s.subtreeWithAllDeepest(root);
    }


}
